package 动态规划;

/**
 * 221. 最大正方形
 *  在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *  思路：这道题采用动态规划的思路去实现》
 *   1：定义状态转移方程：使用一个二维数组dp 用来存储以每个点为右下角的最大正方形边长 （dp[i][j]）
 *   2: 初始化边界条件： 在第一行或者第一列中，如果 matrix[i][j] = 1, 则dp[i][j] = 1, 否则dp[i][j] = 0;
 *   3: 状态转移方程：
 *       对于i > 0 ,j > 0 的情况，如果matrix[i][j] = 1, 则dp[i][j] 等于其上边、左边、和左上边三个相邻位置的dp值的最小值加1，
 *    即dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;
 *       如果matrix[i][j] = 0, 则dp[i][j] = 0，证明当前位置不能构筑符合条件的正方形；
 *   4: 求解最大值:
 *      在计算dp[i][j] 的同时，定义一个最大值变量，记录最大边长maxSide。
 *   5：计算最大面积：
 *      最大边长 * 最大边长。
 */
public class L_221 {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        // 定义状态转移数组
        int m = matrix.length;
        int n =matrix[0].length;
        int[][] dp =new int[m+1][n+1];
        // 定义最大边长变量
        int maxSide = 0;

        // 初始化第一行与第一列
        // 初始化第一列
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1'){
                dp[i][0] = 1;
                maxSide = 1;
            }
        }
        // 初始化第一列
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == '1'){
                dp[0][j] = 1;
                maxSide = 1;
            }
        }

        // 编写状态转移方程
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 如果当前位置为1，则按照状态转移方程计算
                if (matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1])) + 1;
                    maxSide = Math.max(maxSide,dp[i][j]);
                }else { // 如果当前位置为0，则dp[i][j] = 0
                    dp[i][j] = 0;
                }
            }
        }

        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        L_221 solution = new L_221();
        char[][] matrix = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int result = solution.maximalSquare(matrix);
        System.out.println("最大正方形的面积是: " + result);
    }
}
